package alo.p3.work;

import alo.p3.ListNode;


/*
* 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤m≤n≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
*/
public class ReverseBetween {
    class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if(m==n) return head;
            //设置哑结点
            ListNode s=new ListNode(0);
            s.setNext(head);

            ListNode c1=s,nt=null,temp=null,pre,end;
            for(int i=1;i<m;i++){
                c1=c1.getNext();
            }
            //找到m结点和前结点
            pre=c1;
            end=c1.getNext();
            c1=c1.getNext();
            //逆置m-（n-1）
            while(m<n){
                nt=c1.getNext();
                c1.setNext(temp);
                temp=c1;
                c1=nt;
                m++;
            }
            //连接尾结点
            end.setNext(c1.getNext());
            //连接n-（n-1）
            c1.setNext(temp);
            //连接逆置头结点
            pre.setNext(c1);

            return s.getNext();

        }
    }
}
